Error correction is implemented most commonly in digital communication through an encoding apparatus for developing redundant information in a mathematically prescribed manner for transmission over data channels to eventual transmission to an error correction decoder which detects, locates and corrects combinations of errors in the information stream. The purpose for the redundant information is to correct errors caused by defects in recording tape media which create areas where digital data is not recorded properly or cannot be reliably read back.
During recording, read back and transmission of data, errors occur in digital data with some finite probability. The errors which occur are considered to be of two types, although there is undoubtedly some overlap between the two. The first type is a single bit error which is a substitution of one of two possible values of a binary bit for its opposite value. Such errors usually occur randomly in a digital signal. The second type of error consists of a continuous sequence of erroneous bits. Such errors are referred to as "burst errors". The length of these bursts and their frequency of occurrence is also random.
A typical approach to the inevitable occurrence of such errors in a digital signal is to include additional or redundant bits in the signal which allow for detection and correction of such errors. The process whereby the redundant bits are added to information is called encoding; the information bits plus redundant bits form the code word.
The cost associated with encoding is increased time for processing the data after transmission, the extra equipment needed and the decrease in the amount of information which can be transmitted per unit of time because of the extra bits which are included for error detection and correction. As the number of errors which can be corrected by any code increases, the number of bits which must be added to the data to enable such corrections also increases. Accordingly, there has been considerable effort directed to finding efficient methods for generating and coordinating the creation of these extra redundant bits. Efficiency in this context is measured by the ratio of information or data bits to data bits plus data correction or "parity" bits; it is also measured by the number of errors which can be corrected over a given amount of data (typically expressed as the number of errors remaining after correction of an assumed initial error frequency occurs). From a theoretical view point it has been found that Reed-Solomon class of block codes are among the most efficient coding schemes devised. For a more complete development of the Reed-Solomon codes, refer to McEliece, "The Theory of Information and Coding", Addison-Wesley Publishing Company (1977), which is herein incorporated by reference.
Efficiency of any error correcting code however, in practical use, depends on the implementing equipment. Tape drives cannot stop in mid stream, so a method must be provided for reliably fast response and high overall transfer rates. For tape drives with low average data transfer rates, there are sometimes requirements for very short "latency" time, the time from initial requests to actual movement of data. For example, a short latency time is required to avoid data "under-run" situations, processing at a speed slower than the tape drive can accept the data. In order to match the data throughput to the tape acceptance rate, the tape must be stopped and backed up to the location where the under-run situation begins. This process significantly effects the overall performance of the tape drive. To maximize the efficiency of the data transfer rate, the tape drive must be kept "streaming".
Compounding the problem of data under-run, parity digits for error detection and correction must be calculated which may also cause streaming to halt. More particularly, in a typical process for calculating parity digits and/or appending the digits to the data, a two-step process must occur. First, the data is sent out to the tape drive and then after the data has been stored on tape the parity digits are calculated and sent to tape. This operation takes time away from the constant transfer of data to the tape drive. A significant performance degradation occurs because the tape stops streaming to await the calculation and arrival of the parity digits.